package leetcode_201_300;

import java.util.*;

public class LeeCode_241 {
    public static void main(String[] args) {
//        System.out.println(diffWaysToCompute("2-1-1"));
        System.out.println(diffWaysToCompute("2*3-4*5"));
//        System.out.println(diffWaysToCompute("6-20"));
//        System.out.println(diffWaysToCompute("0+1"));
        System.out.println(diffWaysToCompute("15*1*4"));
    }
    private static List<Integer> diffWaysToCompute(String expression) {
        // +:-3    -:-2    *:-1
        LinkedList<Integer> list = new LinkedList<>();
        String[] split1 = expression.split("\\+");
        for (int k = 0; k < split1.length; k++) {
            String[] split2 = split1[k].split("-");
            for (int j = 0; j < split2.length; j++) {
                String[] split3 = split2[j].split("\\*");
                for (int i = 0; i < split3.length; i++) {
                    list.add(Integer.parseInt(split3[i]));
                    if (i == split3.length - 1)
                        continue;
                    list.add(-1);
                }
                if (j == split2.length - 1)
                    continue;
                list.add(-2);
            }
            if (k == split1.length - 1)
                continue;
            list.add(-3);
        }
        return getAll(list, 0, list.size() - 1);
    }
    private static List<Integer> getAll(LinkedList<Integer> list, int s, int e){
        List<Integer> ans = new ArrayList<>();
        if (s == e){
            ans.add(list.get(s));
            return ans;
        }
        for (int i = s + 1; i <= e; i += 2) {
            List<Integer> ls = getAll(list, s, i - 1);
            List<Integer> rs = getAll(list, i + 1, e);
            for (int m = 0; m < ls.size(); m++) {
                for (int n = 0; n < rs.size(); n++) {
                    switch (list.get(i)){
                        case -3:{
                            ans.add(ls.get(m) + rs.get(n));
                            break;
                        }
                        case -2:{
                            ans.add(ls.get(m) - rs.get(n));
                            break;
                        }
                        case -1:{
                            ans.add(ls.get(m) * rs.get(n));
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }
}
